题目大意：求$\sum_{i=1}^n\sum_{j=1}^md(ij)$ ，其中$d(n)$ 指$n$ 的因子个数。
莫比乌斯反演
$i\times j$ 的每个因数可以被唯一表示为$\frac{pj}{q}$ ，其中$p|i,q|j,(p,q)=1$ ，故$d(ij)=\sum_{p|i}\sum_{q|j}[(p,q)=1]$ 。
$$
\therefore \sum_{i=1}^n\sum_{j=1}^md(ij)=\sum_{i=1}^n\sum_{j=1}^m\sum_{p|i}\sum_{q|j}[(p,q)=1]\\
=\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor\\
=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|(i,j)}u(d)\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor\\
=\sum_{d=1}^{min(n,m)}u(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{jd} \rfloor\\
=\sum_{d=1}^{min(n,m)}u(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{id} \rfloor\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{jd} \rfloor\\
=\sum_{d=1}^{min(n,m)}u(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}d(i)\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} d(j)\\
$$
复杂度$O(nlogn+\sqrt{n})$ 。
代码如下：
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=50000+5;
ll p[N],vis[N]={1,1},k,u[N]={0,1},pu[N],d[N],pd[N];
void init(ll n){
for(ll i=2;i<n;++i){
if(!vis[i]){
p[k++]=i;
u[i]=-1;
}
for(ll j=0;j<k&&p[j]*i<n;++j){
vis[p[j]*i]=1;
if(i%p[j]==0){
u[i*p[j]]=0;
break;
}else u[i*p[j]]=-u[i];
}
}
for(ll i=1;i<n;++i)
pu[i]=pu[i-1]+u[i];
for(ll i=1;i<n;++i)
for(ll j=i;j<n;j+=i)
d[j]++;
for(ll i=1;i<n;++i)
pd[i]=pd[i-1]+d[i];
}
ll Min(ll a,ll b){
return a<b?a:b;
}
ll solve(ll n,ll m){
ll ans=0,len=Min(n,m),d,td;
for(d=1;d<=len;d=td+1){
td=Min(n/(n/d),m/(m/d));
ans+=(pu[td]-pu[d-1])*pd[n/d]*pd[m/d];
}
return ans;
}
int main(void){
init(N);
ll T,n,m;
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);
printf("%lld\n",solve(n,m));
}
}